public class Solution91 {
    public int numDecodings(String s) {
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '0') {
                return 0;
            } else if (i < s.length() - 1 && s.charAt(i + 1) == '0') {
                if (c == '1' || c == '2') {
                    dp[i + 1 + 1] = dp[i];
                    i++;
                } else {
                    return 0;
                }
            } else {
                if (i > 0 && (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && c <= '6'))) {
                    dp[i + 1] = dp[i] + dp[i - 1];
                } else {
                    dp[i + 1] = dp[i];
                }
            }
        }
        return dp[s.length()];
    }
}
